package a04_字符串;

import java.util.Arrays;

/**
 * <p>
 * a07_重复的子字符串
 * kmp题解
 * abababab
 * 最长相等前后缀不包含的部分
 * 首先说最长相等前后缀为ababab
 * 不包含的即是ab
 * 推导开始：
 * 假设t为最长相等前缀
 * f为最长相等后缀
 * 则t = f
 * t0 = f0，t1 = f1
 * t01 = f01
 * 则原来字符串的s01 = t23
 * f0和t2在同一个位置
 * f0 = t2
 * f1 = t3
 * f01 = t23
 * f01 = f23
 * 推导结束：
 * </p>
 *
 * @author flyduck
 * @since 2024-07-11
 */
public class a07_重复的子字符串 {

    public static void main(String[] args) {
        String s = "abac";
        System.out.println(repeatedSubstringPattern(s));
    }
    public static boolean repeatedSubstringPattern(String s) {
        int[] nextArray = new int[s.length()+1];
        getNextArray(nextArray,s);
        //计算下一个的值
        if(nextArray[nextArray.length - 1] > 0){
            return s.length() % (s.length() - nextArray[nextArray.length - 1]) == 0;
        }
        return false;

    }

    //aabaat x aabaat x a
    //                6 currentIdx
    private static void getNextArray(int[] nextArray,String str){
        char[] chars = str.toCharArray();
        if(chars.length == 0){
            nextArray[0] = -1;
            return;
        }
        nextArray[0] = -1;
        nextArray[1] = 0;

        int currentIdx = 2;
        int compareIdx = nextArray[currentIdx - 1];

        while (currentIdx < nextArray.length) {
            if(chars[currentIdx - 1] == chars[compareIdx]){//相等
                nextArray[currentIdx] = compareIdx + 1;
                currentIdx++;
                compareIdx = nextArray[currentIdx - 1];
            }else {
                if(nextArray[compareIdx] == -1){//compareIdx是一个元素了
                    nextArray[currentIdx] = 0;
                    currentIdx++;
                    compareIdx = nextArray[currentIdx - 1];
                }else {//继续跳
                    compareIdx = nextArray[compareIdx];
                }
            }
        }

        //注意：ll
    }
}
